package algorithm.math;

/**
 * leetcode : https://leetcode.com/problems/powx-n/description/
 * Difficulty : Medium
 *
 * 求数字的幂次
 * pow(x,n) = x^n
 *
 * 使用递归的方法，并且充分利用已经求得的数
 * 偶数 pow(x,n) = pow(x,n/2) * pow(x, n/2)
 * 奇数 再乘一个 x
 *
 * 题的TestCase 很恶心，边界值处理很麻烦，代码正确，但是整数边界值处理没过。不写了
 * @Author Antony
 * @Since 2018/7/20 14:15
 */
public class Pow {

    public static void main(String[] args) {
        int x = 2;
        int n = -2;
        System.out.println(myPow(x,n));

    }

    public static double myPow(double x, int n) {
        if(n==0) return 1;
        if(x==0) return 0;
        if(n==1) return x;
        if(n < 0){
            x = 1/x;
            n = 0-n;
        }
        double tmp = myPow(x, n/2);
        double result;
        if(n%2 == 1){
            result = tmp*tmp*x;
        }else{
            result = tmp*tmp;
        }

        return result;
    }
}
